PGCD dépendant d'une variable - Corrigé

Énoncé

Soit $n\in \mathbb{Z}$ . On pose $a=2n-5$ et $b=5n-9$ .

1. À l'aide de la calculatrice, calculer le PGCD de $a$ et $b$ pour $n$ variant de $0$ à $15$ .

2. Calculer $5a-2b$ . En déduire que le PGCD de $a$ et $b$ est $1$ ou $7$ .

3. Déterminer les entiers relatifs $n$ tels que $2n-5\equiv 0[7]$ .

4. En déduire $\mathrm{PGCD}(a;b)$ selon les valeurs de $n$ .

Solution

1. D'après la calculatrice, on trouve les valeurs suivantes :
$\begin{array}{r}\begin{array}{|ccccccccccccccccc|}\hline n& 0& 1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12& 13& 14& 15\\ \mathrm{PGCD}(a;b)& 1& 1& 1& 1& 1& 1& 7& 1& 1& 1& 1& 1& 1& 7& 1& 1\\ \hline\end{array}\end{array}$  

2. On a  $\begin{array}{r}5a-2b=5(2n-5)-2(5n-9)=10n-25-10n+18=-7.\end{array}$  

On note $d=\mathrm{PGCD}(a;b)$ . Comme $d$ est un diviseur commun à $a$ et $b$ , $d$ divise toute combinaison linéaire de $a$ et $b$ , notamment $5a-2b$ .

On en déduit que $d$ divise $-7$  et, comme $d⩾1$ , les seules possibilités sont $d=1$ ou $d=7$ .

3. Pour tout $n\in \mathbb{Z}$ , $2n-5\equiv 0[7]⟺2n\equiv 5[7]$ . On fait le tableau des congruences de $2n$ modulo $7$ :
$\begin{array}{r}\begin{array}{|cccccccc|}\hline n\equiv ...[7]& 0& 1& 2& 3& 4& 5& 6\\ 2n\equiv ...[7]& 0& 2& 4& 6& 1& 3& 5\\ \hline\end{array}\end{array}$  

On en déduit que, pour tout $n\in \mathbb{Z}$ , $2n-5\equiv 0[7]$ si, et seulement si, $n\equiv 6[7]$ .

4. D'après la question 2., $d=\mathrm{PGCD}(a;b)$ vaut $1$ ou $7$ . D'après la question 3., $a=2n-5$ est divisible par $7$ si, et seulement si, $n\equiv 6[7]$ .
On en déduit que, si $n$ n'est pas congru à $6$ modulo $7$ , alors $d=\mathrm{PGCD}(a;b)=1$ car $7$ ne divise pas $a$ .Il reste à vérifier si $b$ est divisible par $7$ lorsque $n\equiv 6[7]$ .

Supposons donc que $n\equiv 6[7]$ . On a alors  $\begin{array}{r}b\equiv 5n-9\equiv 5\times 6-9\equiv 30-9\equiv 21\equiv 0[7]\end{array}$  
donc $b$ est divisible par $7$ . Comme $a$ est aussi divisible par $7$ dans ce cas, on en déduit que $d=\mathrm{PGCD}(a;b)=7$ .

En résumé :  $\begin{array}{r}\mathrm{PGCD}(a;b)=\{\begin{array}{ll}7& \text{ si }n\equiv 6[7]\\ 1& \text{ sinon.}\end{array}\end{array}$